package net.cyndeline.rldungeon.dgs.strategy.pointlessArea.algorithms

import scalax.collection.immutable.Graph
import com.escalatesoft.subcut.inject.{Injectable, BindingModule}
import net.cyndeline.rldungeon.dgs.graph.Room
import scala.reflect.ClassTag
import scalax.collection.GraphTraversal.VisitorReturn._
import net.cyndeline.rldungeon.dgs.strategy.help.{CollapsedEdge, CollapsedNode}
import net.cyndeline.rldungeon.dgs.strategy.pointlessArea.algorithms.help.PointlessAreaResult

/**
 * Used for injection.
 */
trait PointlessAreaDesignatorI {
  def computePointlessAreas[VType <: Room[VType] : ClassTag]
                           (graph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner],
                            startToGoalPath: List[CollapsedNode[VType]]): List[PointlessAreaResult[VType]]
}
/**
 * Computes pointless areas on a cycle-collapsed graph.
 */
class PointlessAreaDesignator(implicit val bindingModule: BindingModule)
  extends PointlessAreaDesignatorI
  with Injectable {

  /**
   * Searches for paths in a cycle-collapsed graph that diverges from the main path between start and goal of the level.
   *
   * @param graph An acyclic graph where vertices have been collapsed into super-nodes.
   * @param startToGoalPath A list of vertices from the level start room to the goal room (both inclusive).
   * @return A list of pointless area representations containing which rooms belong to each area, and which room the
   *         area connects to on the main path.
   */
  def computePointlessAreas[VType <: Room[VType] : ClassTag]
                           (graph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner],
                            startToGoalPath: List[CollapsedNode[VType]]): List[PointlessAreaResult[VType]] = {
    var allPointlessAreas = Set[PointlessAreaResult[VType]]()
    val mainPathSet = startToGoalPath.toSet
    val nodesOnMainPath = startToGoalPath.toIterator

    while (nodesOnMainPath.hasNext) {
      val mainNode = nodesOnMainPath.next()
      val neighborsOutsidePath = graph.get(mainNode).neighbors.filter(n => !mainPathSet.contains(n)).toIterator

      /* Begin a traversal of all nodes in the graph, starting at the neighbor of the main node. Since the collapsed
       * graph is a tree, only the pointless area connected to the neighbor will be traversed if the main node is set
       * as un-traversable.
       */
      while (neighborsOutsidePath.hasNext) {
        val neighbor = neighborsOutsidePath.next()

        /* The vertex being represented by the collapsed node whose pointless neighbor is currently being processed. */
        val representedVertexOnMainPath =
          if (!mainNode.isSuperNode) {
            mainNode.vertexCollection.head
          } else {
            val edgeConnectingNeighbor = graph.edges.find(e =>
              (e._1 == mainNode && e._2 == neighbor) || (e._2 == mainNode && e._1 == neighbor)).getOrElse {
              throw new Error("No edge between " + mainNode + " and " + neighbor + " found in " + graph)
            }

            val originalTarget = if (edgeConnectingNeighbor._1 == mainNode) edgeConnectingNeighbor.originalFrom
                               else edgeConnectingNeighbor.originalTo

            originalTarget.get
          }

        /* Method that traverses nodes in a graph and adds the vertices they represent to the set of pointless rooms. */
        var verticesInArea = Set[VType]()
        var nodesInArea = Set[CollapsedNode[VType]]()
        def addToSet(n: graph.NodeT) = {
          verticesInArea ++= n.vertexCollection
          nodesInArea += n
          Continue
        }

        /* Add all nodes that can be reached from the pointless neighbor (without traversing the main node) to a set. */
        neighbor.withSubgraph(_ != mainNode).foreach(addToSet(_))
        allPointlessAreas += PointlessAreaResult[VType](verticesInArea, representedVertexOnMainPath, nodesInArea, mainNode)
      }
    }

    allPointlessAreas.toList
  }

}
